#include "mcbsp.hpp"
#include <stdio.h>

#include <string>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <memory>
#include <cstring>
#include <cassert>

using std::ifstream;
using std::string;
using std::vector;
using std::max;

#pragma GCC diagnostic ignored "-Wsign-compare"
#define COLS_PER_CLOCK 15

int P;
string cols_str, rows_str;
int res;

template<typename T>
struct Array {
	T* const p;
	int size;
	void clear() {	memset(p, 0, size*sizeof(T)); }
	Array(int size) : p(new T[size]), size(size) {
		clear();
	}
	void assign(const T* arr) {
		std::memmove(this->p, arr, sizeof(T) * this->size) ;
	}
	T& operator[](int i) { return p[i]; }
	operator T*() { return p; }
	~Array() {	delete[] p;	}
};

template<typename T>
struct SharedArray : Array<T> {
	SharedArray(int size) : Array<T>(size) {
		bsp_push_reg(this->p, sizeof(T)*(size));
		bsp_sync();
	}

	void get(int from_pid, Array<T>& into, int count) {
		int msg_size = count*sizeof(T);
		assert(into.size*sizeof(T) >= msg_size);
		assert(this->size*sizeof(T) >= msg_size);
		bsp_get(from_pid, this->p, 0, into.p, msg_size);
	}

	~SharedArray() {
		bsp_pop_reg(this->p);
	}
};

template<typename T>
void broadcast(T* p, int count=1, int source_pid = 0) {
	bsp_push_reg(p, sizeof(T)*count);
	bsp_sync();
	bsp_get(source_pid, p, 0, p, sizeof(T)*count);
	bsp_sync();
	bsp_pop_reg(p);
	bsp_sync();
}

void copy_string(string& s) {
	int size = s.size();
	broadcast(&size);

	Array<char> res(size);
	if (bsp_pid()==0)
		res.assign(s.c_str());
	broadcast(res.p, size);
	s.assign(res, size);
}

struct Block {
	const int cols_per_block, rows_per_block, row;

	Array<int> up, left;
	SharedArray<int> down;

	int from_pid() {
		return bsp_pid()-1;
	}

	int index() {
		return bsp_pid();
	}

	int get_rows_per_block(int index) {
		return get_row(index+1)-get_row(index);
	}
	int get_row(int index) {
		if (index == bsp_nprocs())
			return rows_str.size();
		return (rows_str.size() / bsp_nprocs()) * index;
	}

	Block()  :
		cols_per_block(COLS_PER_CLOCK),//cols_str.size() / NCOLS),
		rows_per_block(get_rows_per_block(index())),
		row(get_row(index())),
		up(cols_per_block + 1),
		left(rows_per_block),
		down(cols_per_block + 1)
	{
	}

	void lcs(const char* rows, const char* cols, int ncols) {
		int* prev = down;
		int* cur = up;
		for (int i = 0; i < rows_per_block; i++) {
			std::swap(prev, cur);
			cur[0] = left[i];
			for (int j = 1; j <= ncols; j++) {
				cur[j] = (cols[j - 1] == rows[i])
						? prev[j - 1] + 1 : max(cur[j - 1], prev[j]);
			}
			left[i] = cur[ncols];
			//print_array("cur", cur, cols_per_block);
		}
		down.assign(cur);
	}

	void exchange_data(int ncols) {
		if (index() != 0)
			down.get(from_pid(), up, ncols + 1);
		bsp_sync();
		if (index() == 0)
			up.clear();
	}

};


void lcs() {
	copy_string(rows_str);
	copy_string(cols_str);
	Block m;

	int count = bsp_nprocs();
	for (int i = 0; i <= m.index(); i++, count--)
		bsp_sync();

	const int colsize = cols_str.size();

	for (int col = 0; col < colsize; col += m.cols_per_block) {
		int ncols = std::min(colsize - col, m.cols_per_block);
		m.exchange_data(ncols);
		m.lcs(&rows_str[m.row], &cols_str[col], ncols);
	}
	while (count--)
		bsp_sync();

	int local_res = m.left[m.rows_per_block-1];
	broadcast(&local_res, 1, bsp_nprocs()-1);
	res = local_res;
}

template<void f(void)>
void spmd() {
	bsp_begin(P);
	try {
		f();
	} catch (...) {
		printf("Exception!\n");
	}
	bsp_end();
}

int main(int argc, char *argv[]) {
	bsp_init(spmd<lcs>, argc, argv);
	if (argc != 4) {
		bsp_abort((char*)"Usage: ./lcs <num of processes> <file name 1> <file name 2>\n");
		return 1;
	}
	sscanf(argv[1], "%d", &P);
	typedef std::istreambuf_iterator<char> buf_t;
	cols_str = string(buf_t(std::ifstream(argv[2]).rdbuf()), buf_t());
	rows_str = string(buf_t(std::ifstream(argv[3]).rdbuf()), buf_t());

	spmd<lcs>();

	printf("%d\n", res);
}

